package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)441. 排列硬币
 * (done)598. 范围求和 II
 * (done)970. 强整数
 * @author: jie.deng
 * @time: 2019年3月1日 上午9:32:35
 */
public class MySolution0301 {

	/**
	 * 441. 排列硬币
	 * 
	 * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
	 * 
	 * 给定一个数字 n，找出可形成完整阶梯行的总行数。
	 * 
	 * n 是一个非负整数，并且在32位有符号整型的范围内。
	 * 
	 * 示例 1:
	 * 
	 * n = 5
	 * 
	 * 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤
	 * 
	 * 因为第三行不完整，所以返回2. 示例 2:
	 * 
	 * n = 8
	 * 
	 * 硬币可排列成以下几行: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤
	 * 
	 * 因为第四行不完整，所以返回3.
	 * 
	 * @param n
	 * @return
	 */
	public int arrangeCoins(int n) {
		// (1+x)x/2 <=n && (1+x+1)(1+x)/2 > n
		if (n == 0) {
			return n;
		}
		int x = (int) (Math.sqrt(n) * Math.sqrt(2));
		// [1,x-1]的和
		int sum = 0;
		if (x % 2 == 0) {
			sum = x / 2 * (x - 1);
		} else {
			sum = x * ((x - 1) / 2);
		}
		while (sum <= n - x) {
			sum += x;
			x++;
		}
		return x - 1;
	}



	/**
	 * 598. 范围求和 II
	 * 
	 * 给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
	 * 
	 * 操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b
	 * 的元素 M[i][j] 的值都增加 1。
	 * 
	 * 在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。
	 * 
	 * 示例 1:
	 * 
	 * 输入: m = 3, n = 3 operations = [[2,2],[3,3]] 输出: 4 解释: 初始状态, M = [[0, 0,
	 * 0], [0, 0, 0], [0, 0, 0]]
	 * 
	 * 执行完操作 [2,2] 后, M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]]
	 * 
	 * 执行完操作 [3,3] 后, M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]]
	 * 
	 * M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。 注意:
	 * 
	 * m 和 n 的范围是 [1,40000]。 a 的范围是 [1,m]，b 的范围是 [1,n]。 操作数目不超过 10000。
	 * 
	 * @param m
	 * @param n
	 * @param ops
	 * @return
	 */
	public int maxCount(int m, int n, int[][] ops) {
		if (ops == null || ops.length == 0) {
			return m*n;
		}
		int minA = m;
		int minB = n;
		for (int row = 0; row < ops.length; row++) {
			if (ops[row][0] < minA) {
				minA = ops[row][0];
			}
			if (ops[row][1] < minB) {
				minB = ops[row][1];
			}
		}
		return minA * minB;
	}

	/**
	 * 970. 强整数
	 * 
	 * 给定两个非负整数 x 和 y，如果某一整数等于 x^i + y^j，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个强整数。
	 * 
	 * 返回值小于或等于 bound 的所有强整数组成的列表。
	 * 
	 * 你可以按任何顺序返回答案。在你的回答中，每个值最多出现一次。
	 * 
	 * 
	 * 
	 * 示例 1：
	 * 
	 * 输入：x = 2, y = 3, bound = 10 输出：[2,3,4,5,7,9,10] 解释： 2 = 2^0 + 3^0 3 = 2^1
	 * + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 +
	 * 3^2 示例 2：
	 * 
	 * 输入：x = 3, y = 5, bound = 15 输出：[2,4,6,8,10,14]
	 * 
	 * 
	 * 提示：
	 * 
	 * 1 <= x <= 100 1 <= y <= 100 0 <= bound <= 10^6
	 * 
	 * @param x
	 * @param y
	 * @param bound
	 * @return
	 */
	public List<Integer> powerfulIntegers(int x, int y, int bound) {
		// 注意x=1或者y=1的情况
		List<Integer> listX = new ArrayList<Integer>();
		int sum = 1;
		if (x != 1) {
			while (sum <= bound) {
				listX.add(sum);
				sum *= x;
			}
		} else {
			listX.add(sum);
		}
		List<Integer> listY = new ArrayList<Integer>();
		sum = 1;
		if (y != 1) {
			while (sum <= bound) {
				listY.add(sum);
				sum *= y;
			}
		} else {
			listY.add(sum);
		}
		Set<Integer> set = new HashSet<Integer>();
		for (Integer sumX : listX) {
			for (Integer sumY : listY) {
				if (sumX + sumY > bound) {
					break;
				}
				set.add(sumX + sumY);
			}
		}
		return new ArrayList<Integer>(set);
	}
}
